package com.frx.leetoffer.recursion;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ：frx
 * @date ：Created in 2019/11/3 16:29
 * @description： 经典的爬楼梯问题
 * @modified By：
 * @version: ToDO
 */
public class ClimbStairs {
    private static Map<Integer,Integer> map = new HashMap<>();
    public static void main(String[] args){
        System.out.println(climb(10));
        System.out.println(dpClimb(10));
    }

    public static int climb(int n){
        if (n==1){
            return 1;
        } else if (n == 2){
            return 2;
        } else {
            if (map.containsKey(n)){
                return map.get(n);
            } else {
                int val = climb(n-1) + climb(n-2);
                map.put(n,val);
                return val;
            }
        }
    }

    public static int dpClimb(int n){
        int a = 1;
        int b = 2;
        int temp = 0;
        for (int i=3;i<=n;i++){
            temp = a+b;
            a = b;
            b = temp;
        }

        return temp;
    }

}
